class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len<=1) return len;
        int nums1[len];
        for(int i=0;i<len;i++){
          nums1[i]=0;
        }
        nums1[0] = nums[0];
        int j = 0;
        for(int i=1;i<len;i++){
            if(nums[i] > nums1[j]){
              j++;
              nums1[j] = nums[i];
            }else{
              int l = 0,r = j;
              while(l<r){
                int mid=(l+r)/2;
                if(nums1[mid]>=nums[i]){
                  r=mid;
                }else{
                  l=mid+1;
                }
              }
              nums1[l]=nums[i];
            }
        }
        for(int i=0;i<len;i++){
          if(nums1[i]==0&&i>0){
            return i;
          }
        }
        return len;
    }
};
